#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Edge {
	int cost, v, nxt;
} e[500010];
int cnt, heads[10010];
inline void add(int u, int v, int c) {
	e[++cnt].nxt = heads[u];
	e[cnt].v = v;
	e[cnt].cost = c;
	heads[u] = cnt;
}
int n, m, s;
priority_queue< pair< int, int > > q;
int dis[10010];
int main() {
	// freopen("testdata.in", "r", stdin);
	// freopen("testdata.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; ++i) {
		dis[i] = 0x7fffffff;
	}
	dis[s] = 0;
	int t1, t2, t3;
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", &t1, &t2, &t3);
		add(t1, t2, t3);
	}
	q.push(make_pair(0, s));
	while (!q.empty()) {
		int x = q.top().second;
		int d = -q.top().first;
		q.pop();
		if (d != dis[x]) continue;
		for (int i = heads[x]; i; i = e[i].nxt) {
			if (dis[e[i].v] > dis[x] + e[i].cost) {
				dis[e[i].v] = dis[x] + e[i].cost;
				q.push(make_pair(-dis[e[i].v], e[i].v));
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d ", dis[i]);
	}
	return 0;
}